The invention relates to the field of error correction codes, and in particular to applications traditionally requiring product error correction codes.
An error correction code (ECC) assists in locating errors in digital data, and allows a predetermined number of errors to be corrected. The ability to detect and correct errors is accomplished by adding redundant information to the data according to a specific algorithm. Each bit of redundant information is generated based on the original data bits.
Block error correction codes are used for fixed-size blocks of data. Examples of block error correction codes include Reed-Solomon, Golay, and Hamming codes. Block codes are widely used to protect the accuracy of data stored on digital storage media, or transmitted digitally.
In error correction coding, each block of data may be organized into rows and columns. In order to increase the number and range of possible errors that can be corrected by the ECC scheme in a block of data, error correction data is often calculated both for each row and for each column of data in the block. This method of using both row and column error correction codes in a single block of data is referred to as a product code or a two dimensional block error correction code. The increase in ability to correct errors using a product code also introduces an increase in the amount of redundant information added to the data since ECC data must be added for both rows and columns. This increase in the amount of error correction data in turn decreases the amount of original user data that can be stored or transmitted.
As illustrated in FIG. 1, user data 30, protected by a product code ECC scheme, is organized into rows and columns (see rows 1-U and columns 1-V). Each column is typically one byte of data but may be any number of bits pertaining to an ECC symbol (10 bits for example). It should be noted that user data itself may already include some type of error correction or error detection code such as a cyclic redundancy check (CRC). ECC data is calculated for each row of user data according to the ECC scheme employed, which may be Reed-Solomon, Golay, Hamming, or any other block ECC. This data is then appended to the end of each row. Additional ECC data is also calculated for each column, and placed at the bottom of each column. This entire block, including both user and ECC data, can then be stored or transmitted. The symbols are typically stored or transmitted beginning with the symbol occupying row 1 (20), column 1 (10), followed by the remaining symbols in row 1 (20), proceeding towards column Y (14). Each row is then stored or transmitted in a similar order, proceeding towards row X (24) until the entire block has been completed.
Some errors can be corrected using only the row ECC data, but if an individual row contains too many errors for the respective row ECC scheme to correct, then the column ECC data must also be used to correct the errors. This means that in most cases the entire block is accessed whenever any of the user data is accessed.
Many applications frequently involve errors that require both the row and column ECC data to correct. Errors due to scratches or other defects in digital storage media, or due to certain types of interference in either wired or wireless digital communications are more likely to occur in groups than individually. Although using a product code as described can correct a large amount of contiguous errors, a significant overhead of additional ECC data is introduced by the scheme. This data overhead decreases the actual user data storage capacity or throughput and increases the overall complexity of the system.